Proto-v E B Tree Algorithm

Proto-Germanic developed from pre-Proto-Germanic into three branches during the first half of the first millennium of the common Era: West Germanic, East Germanic and North Germanic, which however remained in contact over a considerable time, particularly the Ingvaeonic languages (including English), which arise from West Germanic dialects and remained in continued contact with North Germanic. While Proto-Germanic refers only to the reconstruction of the most recent common ancestor of Germanic languages, the Germanic parent language refers to the entire journey that the dialect of Proto-Indo-European that would become Proto-Germanic underwent through the millennia.
/*
 Petar 'PetarV' Velickovic
 Data Structure: Proto-vEB Tree
*/

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <complex>
using namespace std;
typedef long long lld;
typedef unsigned long long llu;

/*
 Proto-vEB Tree structure for holding a set of integers in a given universe.
 Complexity:    O(log log u) for member
                O(log u) for insert, delete, min, max, extractMin, first and decreaseKey
                O(log u log log u) for pred, succ
*/

class Proto_vEBTree
{
    llu u;
    Proto_vEBTree *summary; // used if u != 2
    Proto_vEBTree **cluster; // used if u != 2
    
    bool low, high; // used only when u == 2
    int n; // alternative for speeding up proto-vEB-Delete
public:
    Proto_vEBTree(llu);
    
    bool member(llu);
    bool insert(llu);
    bool Delete(llu);
    llu min();
    llu max();
    llu pred(llu);
    llu succ(llu);
    
    llu extractMin();
    llu first();
    void decreaseKey(llu, llu);
};

Proto_vEBTree::Proto_vEBTree(llu u)
{
    this -> u = u;
    this -> n = 0;
    if (u == 2)
    {
        this -> low = this -> high = false;
        this -> summary = NULL;
        this -> cluster = NULL;
    }
    else
    {
        llu subSize = (llu)sqrt(u);
        this -> summary = new Proto_vEBTree(subSize);
        this -> cluster = new Proto_vEBTree*[subSize];
    }
}

bool Proto_vEBTree::member(llu x)
{
    if (u == 2)
    {
        if (x == 0) return low;
        else if (x == 1) return high;
        return false;
    }
    else
    {
        llu subSize = (llu)sqrt(u);
        llu hi = x / subSize, lo = x % subSize;
        if (cluster[hi] == NULL) return false;
        else return cluster[hi] -> member(lo);
    }
}

bool Proto_vEBTree::insert(llu x)
{
    if (u == 2)
    {
        if (x == 0)
        {
            if (low) return false;
            low = true;
            n++;
            return true;
        }
        else if (x == 1)
        {
            if (high) return false;
            high = true;
            n++;
            return true;
        }
        else throw -1;
    }
    else
    {
        llu subSize = (llu)sqrt(u);
        llu hi = x / subSize, lo = x % subSize;
        if (cluster[hi] == NULL)
        {
            cluster[hi] = new Proto_vEBTree(subSize);
            cluster[hi] -> insert(lo);
            n++;
            summary -> insert(hi);
            return true;
        }
        else return cluster[hi] -> insert(lo);
    }
}

bool Proto_vEBTree::Delete(llu x)
{
    if (u == 2)
    {
        if (x == 0)
        {
            low = false;
            n--;
            return !high;
        }
        else if (x == 1)
        {
            high = false;
            n--;
            return !low;
        }
        else throw -1;
    }
    else
    {
        llu subSize = (llu)sqrt(u);
        llu hi = x / subSize, lo = x % subSize;
        if (cluster[hi] -> Delete(lo))
        {
            delete cluster[hi];
            cluster[hi] = NULL;
            n--;
            if (n == 0)
            {
                summary -> Delete(hi);
                return true;
            }
            return false;
        }
        return false;
    }
}

llu Proto_vEBTree::min()
{
    if (u == 2)
    {
        if (low) return 0;
        else if (high) return 1;
        else throw -1; // Proto-vEB is empty
    }
    else
    {
        llu subSize = (llu)sqrt(u);
        llu hi = summary -> min();
        llu lo = cluster[hi] -> min();
        return hi * subSize + lo;
    }
}

llu Proto_vEBTree::max()
{
    if (u == 2)
    {
        if (high) return 1;
        else if (low) return 0;
        else throw -1; // Proto-vEB is empty
    }
    else
    {
        llu subSize = (llu)sqrt(u);
        llu hi = summary -> max();
        llu lo = cluster[hi] -> max();
        return hi * subSize + lo;
    }
}

llu Proto_vEBTree::pred(llu x)
{
    if (u == 2)
    {
        if (x == 1 && low) return 0;
        else throw -1; // Predecessor does not exist
    }
    else
    {
        llu subSize = (llu)sqrt(u);
        llu hi = x / subSize;
        llu lo = x % subSize;
        if (cluster[hi] == NULL)
        {
            llu prev = summary -> pred(hi);
            return prev * subSize + cluster[prev] -> max();
        }
        else
        {
            llu newLo, newHi = hi;
            try
            {
                newLo = cluster[hi] -> pred(lo);
            }
            catch (int e)
            {
                newHi = summary -> pred(hi);
                newLo = cluster[newHi] -> max();
            }
            return newHi * subSize + newLo;
        }
    }
}

llu Proto_vEBTree::succ(llu x)
{
    if (u == 2)
    {
        if (x == 0 && high) return 1;
        else throw -1; // Successor does not exist
    }
    else
    {
        llu subSize = (llu)sqrt(u);
        llu hi = x / subSize;
        llu lo = x % subSize;
        if (cluster[hi] == NULL)
        {
            llu next = summary -> succ(hi);
            return next * subSize + cluster[next] -> min();
        }
        else
        {
            llu newLo, newHi = hi;
            try
            {
                newLo = cluster[hi] -> succ(lo);
            }
            catch (int e)
            {
                newHi = summary -> succ(hi);
                newLo = cluster[newHi] -> min();
            }
            return newHi * subSize + newLo;
        }
    }
}

llu Proto_vEBTree::extractMin()
{
    llu ret = this -> min();
    this -> Delete(ret);
    return ret;
}

llu Proto_vEBTree::first()
{
    return this -> min();
}

void Proto_vEBTree::decreaseKey(llu x, llu y)
{
    // Preconditions: y < x, x is in the tree, y is not in the tree
    
    this -> Delete(x);
    this -> insert(y);
}

int main()
{
    Proto_vEBTree *vEB = new Proto_vEBTree(16);
    vEB -> insert(2);
    vEB -> insert(3);
    vEB -> insert(4);
    vEB -> insert(5);
    vEB -> insert(7);
    vEB -> insert(14);
    vEB -> insert(15);
    printf("%llu\n", vEB -> min());
    printf("%llu\n", vEB -> max());
    printf("%llu\n", vEB -> pred(9));
    printf("%llu\n", vEB -> succ(9));
    return 0;
}

LANGUAGE:

DARK MODE: